#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <queue>

using namespace std;

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<int> word_dict_length;
        unordered_set<int> word_dict_length_map;
        unordered_set<string> word_dict_map;
        for (auto item: wordDict) {
            word_dict_length_map.insert(item.length());
            word_dict_map.insert(item);
        }
        word_dict_length.assign(word_dict_length_map.begin(), word_dict_length_map.end());
        sort(word_dict_length.begin(), word_dict_length.end());
        unordered_set<int> mem;
        mem.insert(0);
        while (mem.size() > 0) {
            unordered_set<int> next_mem;
            for (auto iter: mem) {
                for (auto word_dict_len: word_dict_length) {
                    if (iter + word_dict_len > s.length()) {
                        break;
                    }
                    if ((mem.count(iter + word_dict_len) == 0 && next_mem.count(iter + word_dict_len) == 0) && word_dict_map.count(s.substr(iter, word_dict_len)) != 0) {
                        if (iter + word_dict_len == s.size()) {
                            return true;
                        }
                        next_mem.insert(iter + word_dict_len);
                    }
                }
            }
            mem = next_mem;
        }
        return false;
    }
};

int main() {
    string s = "a";
    vector<string> word_dict = {"a"};
    Solution solution;
    bool new_head = solution.wordBreak(s, word_dict);
    cout << new_head << endl;
    return 0;
}